#include "Utils.h"
#include "ListNode.h"
#include "TreeNode.h"
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Issue316 {
public:
	string removeDuplicateLetters(string s) {
		vector<int> count(26,0);// store count of character remines
		vector<bool> handled(26,false);// store whether a character is added to result
		vector<char> stk;// result stack
		for (int i=0;i<s.length();++i)
		{
			int index=s[i]-'a';
			count[index]=count[index]+1;
		}
		stk.push_back('0');

		for (int i=0;i<s.length();++i)
		{
			char c=s[i];
			int index=c-'a';
			count[index]=count[index]-1;

			if (!handled[index])
			{
				while (c<stk.back()&&count[stk.back()-'a']>0)
				{
					handled[stk.back()-'a']=false;
					stk.pop_back();	
				}
				stk.push_back(c);
				handled[index]=true;
			}
		}

		string res="";
		for (int i=1;i<stk.size();++i)
			res+=stk[i];
		return res;
	}
};

int main316(){

	Issue316 sol;

	string s="cbacdcbc";
	string res=sol.removeDuplicateLetters(s);
	cout<<res<<endl;

	return 0;
}